package edu.whu.rose.clock.ssql.subgraph;

import java.util.HashSet;

import com.sleepycat.je.DatabaseException;

import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.ssql.graph.RRadiusSubGraph;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.IntLinkedList;
import edu.whu.rose.clock.ssql.util.IntLinkedNode;

public class SubgraphCache {

	private final GraphMatrix graph;
	private final int capacity;
	private final SubgraphDB sgdb;

	private RRadiusSubGraph[] cache;
	private IntLinkedList queue;
	private int size;
	private HashSet<Integer> deleted;
	private HashSet<Integer> stored;

	private double visit = 0.0;
	private double hit = 0.0;

	private int[] subgraphNum;
	private int[] radiusRecord;

	public SubgraphCache(GraphMatrix graph, int capacity, SubgraphDB sgdb, int radius) {
		this.graph = graph;
		this.cache = new RRadiusSubGraph[graph.getN()];
		this.capacity = capacity;
		this.queue = new IntLinkedList();
		this.deleted = new HashSet<Integer>();
		this.stored = new HashSet<Integer>();
		this.sgdb = sgdb;
		subgraphNum = new int[radius];
		radiusRecord = new int[graph.getN()];
	}

	public void insert(RRadiusSubGraph rrsg) {
		int index = rrsg.getRow() - 1;
		if (size == capacity) {
			IntLinkedNode head = queue.removeHead();
			int i = head.getIndex();
			remove(i);
		}
		cache[index] = rrsg;
		radiusRecord[index] = ((VaryingRadiusSubgraph)rrsg).getRadius();
		queue.insertAtEnd(new IntLinkedNode(index));
		size++;
	}

	public void remove(int index) {
		RRadiusSubGraph rrsg = cache[index];
		cache[index] = null;
		Integer I = new Integer(index);
		if (!stored.contains(I)) {
			this.putIntoDB(rrsg.getRow(), rrsg);
			stored.add(I);
		}
		this.size--;
	}

	public void delete(int row, boolean exist) {
		int index = row - 1;
		Integer I = new Integer(index);
		if (exist) {
			cache[index] = null;
			radiusRecord[index] = 0;
			deleted.add(I);
			if (stored.contains(I)) {
				rmvFromDB(row);
				stored.remove(I);
			}
			queue.deleteAtEnd(index); // ??????????????????????????????????
			size--;
		} else {
			deleted.add(I);
		}
	}

	public RRadiusSubGraph get(int row) {
		int index = row - 1;
		Integer I = new Integer(index);
		if (deleted.contains(I)) {
			return null;
		}
		visit++;
		if (cache[index] != null) {
			queue.switchToEnd(index);
			hit++;
			return cache[index];
		} else {
			RRadiusSubGraph rrsg = getFromDB(row);
			insert(rrsg);
			return rrsg;
		}
	}

	private void putIntoDB(int row, RRadiusSubGraph rrsg) {
		try {
			sgdb.insertSubGraph(row, rrsg);
		} catch (DatabaseException ex) {
			ex.printStackTrace();
		}
	}

	private RRadiusSubGraph getFromDB(int row) {
		try {
			return sgdb.getSubGraph(row);
		} catch (DatabaseException ex) {
			ex.printStackTrace();
			return null;
		}
	}

	private void rmvFromDB(int row) {
		try {
			this.sgdb.removeSubGraph(row);
		} catch (DatabaseException ex) {
			ex.printStackTrace();
		}
	}

	public void reprocess_flush_indexing() {
		VSILCache vsmc = new VSILCache(graph
				.getN(), 5000, sgdb);
		
		int id = 0;
		for (int i = 0; i < graph.getN(); i++) {
			int row = i + 1;
			Integer I = new Integer(i);
			if (this.cache[i] != null) {
				RRadiusSubGraph rrsg = this.cache[i];
				if (stored.contains(I)) {
					rmvFromDB(row);
				}
				id++;
				addEdges(rrsg);
				this.putIntoDB(id, rrsg);
				insertVSMappings(vsmc, rrsg.getVertexes(), id);
			} else {
				if (!deleted.contains(I)) {
					if (stored.contains(I)) {
						RRadiusSubGraph rrsg = getFromDB(row);
						rmvFromDB(row);
						id++;
						addEdges(rrsg);
						this.putIntoDB(id, rrsg);
						insertVSMappings(vsmc, rrsg.getVertexes(), id);
					} else {
						System.err.println("Error: found a missed subgraph ("
								+ row + ")");
						System.exit(1);
					}
				}
			}
		}
		
		vsmc.flush();
		vsmc.statistic();
	}

	private void insertVSMappings(VSILCache vsmc,
			int[] vertexes, int subgraph) {
		for (int i = 0; i < vertexes.length; i++) {
			vsmc.insert(vertexes[i], subgraph);
		}
	}

	private void addEdges(RRadiusSubGraph rrsg) {
		int[] vertexes = rrsg.getVertexes();
		ExpandableIntArray startVertexes = new ExpandableIntArray();
		ExpandableIntArray endVertexes = new ExpandableIntArray();
		for (int i = 0; i < vertexes.length; i++) {
			int startVertex = vertexes[i];
			int[] ends = graph.getEnds(startVertex);
			if (ends == null) {
				// System.err.println("Error: found isolated vertex (" +
				// startVertex + ")");
				continue;
			}
			int[] filteredEnds = merge(ends, vertexes);
			if (filteredEnds == null) {
				continue;
			}
			for (int j = 0; j < filteredEnds.length; j++) {
				startVertexes.add(startVertex);
				endVertexes.add(filteredEnds[j]);
			}
		}
		rrsg.setStartVertexes(startVertexes.toArray());
		rrsg.setEndVertexes(endVertexes.toArray());
	}

	private int[] merge(int[] arr1, int[] arr2) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int low = 0;
		for (int i = 0; i < arr1.length; i++) {
			int mid = 0;
			int top = arr2.length - 1;
			while (low <= top) {
				mid = (low + top) / 2;
				if (arr1[i] > arr2[mid]) {
					low = mid + 1;
				} else if (arr1[i] < arr2[mid]) {
					top = mid - 1;
				} else {
					eia.add(arr1[i]);
					break;
				}
			}
		}
		return eia.toArray();
	}

	public void statistic() {
		System.out.println("Hit rate: " + (100 * hit / visit) + "%");
		for (int i = 0; i < graph.getN(); i++) {
			if (radiusRecord[i] != 0)
				subgraphNum[radiusRecord[i] - 1]++;
		}
		for (int i = 0; i < subgraphNum.length; i++) {
			System.out.println((i+1) + "-radius graph number: " + subgraphNum[i]);
		}
	}

}
